package q_2_1;

import java.util.Arrays;
import java.util.LinkedList;

public class Q_2_1 {

	public static class Node{
		public int v;
		public Node n;
		public Node p;
	}
	
	public static Node convert(LinkedList<Integer> list) {
		Node head = new Node();
		Node tail = head;
		for(int value : list) {
			tail.n = new Node();
			tail.n.p = tail;
			tail = tail.n;
			tail.v = value;
		}
		head = head.n;
		if(head != null) {
			head.p = null;
		}
		return head;
	}
	
	public static LinkedList<Integer> recover(Node head) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		while(head != null) {
			list.add(head.v);
			head = head.n;
		}
		return list;
	}
	
	public static LinkedList<Integer> remove_duplicates(LinkedList<Integer> list) {
		if (list == null) return null;
		Node head = convert(list);
		Node i = head;
		while(i != null) {
			int a = i.v;
			Node j = i.n;
			while(j != null) {
				int b = j.v;
				if (a == b) {
					j.p.n = j.n;
					if(j.n != null) {
						j.n.p = j.p;
					}
				}
				j = j.n; 
			}
			i = i.n;
		}
		return recover(head);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(remove_duplicates(null));
		System.out.println(remove_duplicates(new LinkedList<Integer>()));
		System.out.println(remove_duplicates(new LinkedList<Integer>(Arrays.asList(1))));
		System.out.println(remove_duplicates(new LinkedList<Integer>(Arrays.asList(1, 1))));
		System.out.println(remove_duplicates(new LinkedList<Integer>(Arrays.asList(1, 2))));
		System.out.println(remove_duplicates(new LinkedList<Integer>(Arrays.asList(1, 2, 1))));
		System.out.println(remove_duplicates(new LinkedList<Integer>(Arrays.asList(1, 1, 2))));
		System.out.println(remove_duplicates(new LinkedList<Integer>(Arrays.asList(1, 1, 1))));
		System.out.println(remove_duplicates(new LinkedList<Integer>(Arrays.asList(1, 2, 3))));
	}

}
